package e_union_find.a_union_find_of_quick_find_type;
import java.util.Arrays;

/**
 * quick find 的方式实现的并查集 - 查快并慢 - 不常使用
 *
 * 并查集是一种描述网络状态（属于同一组）数据结构
 * 比如元素之间如果具有某种一致的状态，那么他们之间就构成了一个网络
 * 比如可以解决图中的点与点是否连接的问题，或者用户之间的人脉关系是否重叠
 * <p>
 * 可以进行的操作：
 * union(p,q) - 将 q 加入p 的组中
 * find（p）- 查找p所在的组
 * 可以回答的问题
 * isConnected（p,q）- 两个元素是否相连
 */
public class UnionFind1 {
    private int[] ids; // 为了方便， 索引代表元素id，值代表该元素所属组的id
    private int count; // 包含的元素个数

    /**
     * 传入 size
     * 构造一个以size为大小的并查集，组号从0递增到size-1
     *
     * @param size
     */
    public UnionFind1(int size) {
        this.count = size;
        this.ids = new int[size];
        for (int i = 0; i < size; i++) {
            this.ids[i] = i;
        }
    }

    /**
     * 查找元素id对应的组id  - O(1)
     *
     * @param p
     * @return 组id
     */
    public int find(int p) {
        assert p >= 0 && p < this.count;
        return ids[p];
    }

    /**
     * 判断两个元素id之间是否处于相同的组  - O(1)
     *
     * @param p
     * @param q
     * @return
     */
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

    /**
     * 将p和q所在组联合成一个组  - O(n) 可优化
     * 将q所在的组的所有成员都拉入p所在的组中
     *
     * @param p
     * @param q
     */
    public void union(int p, int q) {
        assert p >= 0 && p < this.count;
        assert q >= 0 && q < this.count;

        int pID = find(p);
        int qID = find(q);

        if (pID == qID) return;

        for (int i = 0; i < this.count; i++) {
            if (ids[i] == qID) {
                ids[i] = pID;
            }
        }
    }

    /**
     * 将所有元素都归入第一个元素的组中 - O(nlogn) ?
     * @param oids
     */
    public void unionAll(int ...oids) {
        assert oids!=null && oids.length > 0;
        int rootId = oids[0];
        assert rootId >= 0 && rootId < this.count;
        for (int i = 0; i < count; i++) {
            if (Arrays.binarySearch(oids, i) >= 0) {
                if (ids[i] != rootId) ids[i] = rootId;
            }
        }
    }

    // TODO test method .. to be deleted
    public void testPrint() {
        System.out.print("ids -> ");
        for (int i = 0; i < count; i++) {
            System.out.print("\t"+ids[i]);
        }
        System.out.println();
    }

}
